package com.he.algorithm.order;

import java.util.Arrays;

/**
 * @description: TODO
 * @Author: HCL
 * @Date: 2024/8/27 8:07
 */
public class SelectSort {

    /**
     * @Description 选择排序：每次选择最小的一个数与前面的数交换位置，排在前面，复杂度为O(n2)
     * 如 7 1 3 9 5 2 6
     * 第一趟：1 7 3 9 5 2 6
     * 第二趟：1 2 3 9 5 7 6
     * 第三趟：1 2 3 5 9 7 6
     * 第四趟：1 2 3 4 6 7 9
     * @Author HCL
     * @Date 2024/8/27 8:08
     * @Param []
     * @Return void
     */
    public static void order(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) { // 注意这里减1，因为最后一个元素在之前的迭代中已经被排好序
            int minIndex = i; //假设当前i位置的元素是最小的
            for (int j = i + 1; j < nums.length; j++) {  // 从i+1位置开始遍历数组，寻找比当前假设的最小元素还要小的元素
                if (nums[j] < nums[minIndex]) {
                    minIndex = j; // 如果找到了一个更小的元素，则更新最小元素的索引为j,
//                    当j = 1时，nums[j] = 1，它小于nums[min_idx] = nums[0] = 7，所以更新min_idx = j = 1。
//                    继续内层循环，但后续的nums[j]（即nums[2]到nums[6]）都不小于nums[min_idx] = 1，所以min_idx保持为1。
                }
            }
            int temp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = temp;

            printArray(nums, i+1);
        }
    }


    // 辅助方法，用于打印数组
    public static void printArray(int[] arr, int sortedCount) {
        System.out.print("Sorted " + sortedCount + " elements: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println(); // 换行
    }

    public static void main(String[] args) {
        int[] nums = {7, 1, 3, 9, 5, 2, 6};
        order(nums);
        System.out.println(Arrays.toString(nums));
    }
}
